ภารกิจของคุณ 🎯
สร้างเครือข่ายไฮเปอร์เลน (Hyper-lane) ที่มีต้นทุนต่ำที่สุด เพื่อเชื่อมต่อดาวเคราะห์ $N$ ดวง ซึ่งกำหนดพิกัดในรูปแบบ 2 มิติ
- เป้าหมาย: เชื่อมต่อดาวเคราะห์ $N$ ดวง (จุดยอด) ทั้งหมดให้สามารถเข้าถึงกันได้ (โดยตรงหรือผ่านทางอ้อม)
- วัตถุประสงค์: หาโครงสร้างเครือข่ายที่ทำให้ต้นทุนรวมต่ำที่สุด
การวิเคราะห์ 🛰️
ต้นทุนของเส้นทาง (ขอบ) คือ ระยะทางยูคลิด:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- สามารถสร้างเส้นทางระหว่างทุกคู่ของดาวเคราะห์สองดวงใด ๆ ได้
- ซึ่งหมายความว่าเรามีกราฟแบบครบถ้วน (หนาแน่น)
แนวทางการแก้ปัญหา ⚙️
นี่คือปัญหาคลาสสิกต้นไม้ครอบคลุมต่ำสุด (MST) ที่รู้จักกันดี
- อัลกอริธึม: คำแนะนำชี้แนะให้ใช้อัลกอริธึมพริม (Prim's Algorithm) (เวอร์ชัน $O(V^2)$) ซึ่งเหมาะอย่างยิ่งกับกราฟหนาแน่น
- จุดเริ่มต้น:เราจะเริ่มอัลกอริธึมจากดาวเคราะห์ลำดับที่ 0 เพื่อให้ผลลัพธ์มีความสม่ำเสมอ c
กราฟแบบครบถ้วน (ด้านซ้าย) มีขอบทุกคู่ที่เป็นไปได้ ส่วนต้นไม้ครอบคลุมต่ำสุด (MST) (ด้านขวา) คือชุดขอบที่มีต้นทุนต่ำที่สุด ที่เชื่อมต่อจุดยอดทั้งหมดไว้ด้วยกัน